package com.wu.reverselist;

/**
 * 输入一个链表，反转链表后，输出新链表的表头。
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * 思路：
 *      1.定义新链表的表头
 *      2.遍历传入的链表，总是将其放置在新链表表头的后面
 *      原始链表：3 -》 4 -》 2 -》 1
 *      新链表：0 -》 3
 *                  0 -》 4 -》 3
 *                          0 -》 2 -》 4 -》 3-》
 *                                  0 -》 1 -》 2 -》 4 -》 3
 *
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        //只有一个元素的话则不用反转
        if (head == null || head.next == null){
            return head;
        }
        //临时定义表头
        ListNode newList = new ListNode(1);
        //定义临时指针 方便后移
        ListNode temp = null;
        ListNode cur = head;
        while (cur != null){
            //临时存放
            temp = cur.next;
            //将cur的下一个节点指向新链表的最前端
            cur.next = newList.next;
            //将cur存放在新链表上
            newList.next = cur;
            //指向下一个节点
            cur = temp;
        }
        //去除头链表
        return newList.next;
    }
}